Analyzing and Tracking Weblog Communities Using Discriminative Collection Representatives.

Logical queries over views Decidability and expressiveness.

A clustering comparison measure using density profiles and its application to the discovery of alternate clusterings.

Mining Disease State converters for Medical Intervention of Diseases.

A Contrast Pattern Based Clustering Quality Index for Categorical Data.

Applications of Emerging Patterns for Microarray Gene Expression Data Analysis.

Incremental Computation of Queries.
With the growth of the Web, there has been a rapid increase in the number of users who need to access online databases without having a detailed knowledge of the schema or of query languages; even relatively simple query languages designed for non-experts are too complicated for them. We describe BANKS, a system which enables keyword-based search on relational databases, together with data and schema browsing. BANKS enables users to extract information in a simple manner without any knowledge of the schema or any need for writing complex queries. A user can get information by typing a few keywords, following hyperlinks, and interacting with controls on the displayed results. BANKS models tuples as nodes in a graph, connected by links induced by foreign key and other relationships. Answers to a query are modeled as rooted trees connecting tuples that match individual keywords in the query. Answers are ranked using a notion of proximity coupled with a notion of prestige of nodes based on inlinks, similar to techniques developed for Web search. We present an efficient heuristic algorithm for finding and ranking query results. 1.
Emerging Pattern Based Classification.

Emerging Patterns.
Abstract. Emerging patterns (EPs) are associations of features whose frequencies increase significantly from one class to another. They have been proven useful to build powerful classifiers and to help establishing diagnosis. Because of the huge search space, mining and representing EPs is a hard task for large datasets. Thanks to the use of recent results on condensed representations of frequent closed patterns, we propose here an exact condensed representation of EPs. We also give a method to provide EPs with the highest growth rates, we call them strong emerging patterns (SEPs). In collaboration with the Philips company, experiments show the interests of SEPs. 1 Introduction The characterization of classes and classification are significant fields of researchin data mining and machine learning. Initially introduced in [5], emerging patterns (EPs) are patterns whose frequency strongly varies between two data sets(i.e., two classes). EPs characterize the classes in a quantitative and qualitative way. Thanks to their capacity to emphasize the distinctions between classes,EPs enable to build classifiers [6] or to propose a help for diagnosis. Nevertheless, mining EPs in large datasets remains a challenge because of the very highnumber of candidate patterns. In this paper, we propose two contributions for the efficient extraction ofemerging patterns. One originality of our approach is to take advantage of recent progresses on the condensed representations of closed patterns [9]. Firstly,we propose an exact condensed representation of the emerging patterns for a dataset. Contrary to the borders approach (Section 2) which provides the EPswith a lower bound of their growth rate, this condensed representation easily enables to know the exact growth rate for each emerging pattern. Secondly, wepropose a method to easily provide the emerging patterns having the best growth rates (we call them &amp;quot; strong emerging patterns &amp;quot;). This work is also justified byrequests from providers of data. In our collaboration with the Philips company, one notices in practice a high number of EPs and the strong emerging patternsare particularly useful to bring more synthetic and more exploitable results.
Evaluation of Inter%2DLaboratory and Cross%2DPlatform concordance of DNA microarrays through Discriminating genes and Classifier transferability.

Mining Sequence Classifiers for Early Prediction.
Supervised learning on sequence data, also known as sequence classification, has been well recognized as an important data mining task with many significant applications. Since temporal order is important in sequence data, in many critical applications of sequence classification such as medical diagnosis and disaster prediction, early prediction is a highly desirable feature of sequence classifiers. In early prediction, a sequence classifier should use a prefix of a sequence as short as possible to make a reasonably accurate prediction. To the best of our knowledge, early prediction on sequence data has not been studied systematically. In this paper, we identify the novel problem of mining sequence classifiers for early prediction. We analyze the problem and the challenges. As the first attempt to tackle the problem, we propose two interesting methods. The sequential classification rule (SCR) method mines a set of sequential classification rules as a classifier. A so-called early-prediction utility is defined and used to select features and rules. The generalized sequential decision tree (GSDT) method adopts a divide-and-conquer strategy to generate a classification model. We conduct an extensive empirical evaluation on several real data sets. Interestingly, our two methods achieve accuracy comparable to that of the stateof-the-art methods, but typically need to use only very short prefixes of the sequences. The results clearly indicate that early prediction is highly feasible and effective. 1
Substructure similarity measurement in chinese recipes.

Logical Queries over Views Decidability and Expressiveness

Semantic knowledge facilities for a web%2Dbased recipe database system supporting personalization.

Advances in Data and Web Management

Evolution and Maintenance of Frequent Pattern Space When Transactions Are Removed.
Abstract. This paper addresses the maintenance of discovered frequent patterns when a batch of transactions are removed from the original dataset. We conduct an in-depth investigation on how the frequent pattern space evolves under transaction removal updates using the concept of equivalence classes. Inspired by the evolution analysis, an effective and exact algorithm TRUM is proposed to maintain frequent patterns. TRUM maintains frequent patterns efficiently by updating only the affected equivalence classes. Experimental results demonstrate that our algorithm outperforms representative state-of-the-art algorithms. 1
Efficient Computation of Iceberg Cubes by Bounding Aggregate Functions.

Mining minimal distinguishing subsequence patterns with gap constraints.
Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a Minimal Distinguishing Subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the maximum gap constraint. We present an efficient algorithm called ConSGapMiner, to mine all MDSs according to a maximum gap constraint. It employs highly efficient bitset and boolean operations, for powerful gap based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports. 1.
Minimum Description Length Principle Generators Are Preferable to Closed Patterns.

Clustering Similarity Comparison Using Density Profiles.
This paper proposes a new method for comparing clusterings both partitionally and geometrically. Our approach is motivated by the following observation: the vast majority of previous techniques for comparing clusterings are entirely partitional, i.e., they examine assignments of points in set theoretic terms after they have been partitioned. In doing so, these methods ignore the spatial layout of the data, disregarding the fact that this information is responsible for generating the clusterings to begin with. We demonstrate that this leads to a variety of failure modes. Previous comparison techniques often fail to differentiate between significant changes made in data being clustered. We formulate a new measure for comparing clusterings that combines spatial and partitional information into a single measure using optimization theory. Doing so eliminates pathological conditions in previous approaches. It also simultaneously removes common limitations, such as that each clustering must have the same number of clusters or they are over identical datasets. This approach is stable, easily implemented, and has strong intuitive appeal. spatial properties as well as their cluster membership assignments. We view a clustering as a partition of a set of points located in a space with an associated distance function. This view is natural, since popular clustering algorithms, e.g., k-means, spectral clustering, affinity propagation, etc., take as input not only a collection of points to be clustered but also a distance function on the space in which the points lie. This distance function may be specified implicitly and it may be transformed by a kernel, but it must be defined one way or another and its properties are crucial to a clustering algorithm’s output. In contrast, almost all existing clustering comparison techniques ignore the distances between points, treating clusterings as partitions of disembodied atoms. While this approach has merit under some circumstances, it seems surprising to ignore the distance func-
Clustering Similarity Comparison Using Density Profiles.
This paper proposes a new method for comparing clusterings both partitionally and geometrically. Our approach is motivated by the following observation: the vast majority of previous techniques for comparing clusterings are entirely partitional, i.e., they examine assignments of points in set theoretic terms after they have been partitioned. In doing so, these methods ignore the spatial layout of the data, disregarding the fact that this information is responsible for generating the clusterings to begin with. We demonstrate that this leads to a variety of failure modes. Previous comparison techniques often fail to differentiate between significant changes made in data being clustered. We formulate a new measure for comparing clusterings that combines spatial and partitional information into a single measure using optimization theory. Doing so eliminates pathological conditions in previous approaches. It also simultaneously removes common limitations, such as that each clustering must have the same number of clusters or they are over identical datasets. This approach is stable, easily implemented, and has strong intuitive appeal. spatial properties as well as their cluster membership assignments. We view a clustering as a partition of a set of points located in a space with an associated distance function. This view is natural, since popular clustering algorithms, e.g., k-means, spectral clustering, affinity propagation, etc., take as input not only a collection of points to be clustered but also a distance function on the space in which the points lie. This distance function may be specified implicitly and it may be transformed by a kernel, but it must be defined one way or another and its properties are crucial to a clustering algorithm’s output. In contrast, almost all existing clustering comparison techniques ignore the distances between points, treating clusterings as partitions of disembodied atoms. While this approach has merit under some circumstances, it seems surprising to ignore the distance func-
Succinct and Informative Cluster Descriptions for Document Repositories.

Regression Cubes with Lossless Compression and Aggregation.
Abstract—As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures will allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data. Index Terms—Aggregation, compression, data cubes, OLAP. 1
Mining Succinct Systems of Minimal Generators of Formal Concepts.
Abstract. Formal concept analysis has become an active field of study for data analysis and knowledge discovery. A formal concept C is determined by its extent (the set of objects that fall under C) and its intent (the set of properties or attributes covered by C). The intent for C, also called a closed itemset, is the maximum set of attributes that characterize C. The minimal generators for C are the minimal subsets of C’s intent which can similarly characterize C. This paper introduces the succinct system of minimal generators (SSMG) as a minimal representation of the minimal generators of all concepts, and gives an efficient algorithm for mining SSMGs. The SSMGs are useful for revealing the equivalence relationship among the minimal generators, which may be important for medical and other scientific discovery; and for revealing the extent-based semantic equivalence among associations. The SSMGs are also useful for losslessly reducing the size of the representation of all minimal generators, similar to the way that closed itemsets are useful for losslessly reducing the size of the representation of all frequent itemsets. The removal of redudancies will help human users to grasp the structure and information in the concepts.
Mining Minimal Distinguishing Subsequence Patterns with Gap Constraints.
Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a Minimal Distinguishing Subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the maximum gap constraint. We present an efficient algorithm called ConSGapMiner, to mine all MDSs according to a maximum gap constraint. It employs highly efficient bitset and boolean operations, for powerful gap based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports. 1.
Integrating Private Databases for Data Analysis.
Abstract. In today’s globally networked society, there is a dual demand on both information sharing and information protection. A typical scenario is that two parties wish to integrate their private databases to achieve a common goal beneficial to both, provided that their privacy requirements are satisfied. In this paper, we consider the goal of building a classifier over the integrated data while satisfying the k-anonymity privacy requirement. The k-anonymity requirement states that domain values are generalized so that each value of some specified attributes identifies at least k records. The generalization process must not leak more specific information other than the final integrated data. We present a practical and efficient solution to this problem. 1
Integrating Private Databases for Data Analysis.
Abstract. In today’s globally networked society, there is a dual demand on both information sharing and information protection. A typical scenario is that two parties wish to integrate their private databases to achieve a common goal beneficial to both, provided that their privacy requirements are satisfied. In this paper, we consider the goal of building a classifier over the integrated data while satisfying the k-anonymity privacy requirement. The k-anonymity requirement states that domain values are generalized so that each value of some specified attributes identifies at least k records. The generalization process must not leak more specific information other than the final integrated data. We present a practical and efficient solution to this problem. 1


Stream Cube An Architecture for Multi%2DDimensional Analysis of Data Streams.


Divide%2Dand%2DApproximate A Novel Constraint Push Strategy for Iceberg Cube Mining.


Mining border descriptions of emerging patterns from dataset pairs.

On the complexity of finding emerging patterns.

On the Complexity of Finding Emerging Patterns.

Incremental Maintenance on the Border of the Space of Emerging Patterns.


Mining Constrained Gradients in Large Databases.
Many data analysis tasks can be viewed as search or mining in a multidimensional space (MDS). In such MDSs, dimensions capture potentially important factors for given applications, and cells represent combinations of values for the factors. To systematically analyze data in MDS, an in-teresting notion, called “cubegrade ” was recently introduced by Imielinski, et al. [IKA02], which focuses on the notable changes in measures in MDS by comparing a cell (which we refer as probe cell) with its gradient cells, namely its ancestors, descendants and siblings. We call such queries gradient analysis queries (GQs). Since an MDS can contain billions of cells, it is important to answer GQs efficiently. In this study, we focus on developing efficient methods for mining GQs constrained by certain (weakly) anti-monotone constraints. Instead of conducting an independent gradient-cell search once per probe cell, which is inefficient due to much repeated work, we propose an efficient algorithm, LiveSet-Driven. This algorithm finds all good gradient-probe cell pairs in one search pass. It utilizes measure-value analysis and dimension-match analysis in a set-oriented manner, to achieve bi-directional pruning between the sets of hopeful probe cells and of hopeful gradient cells. Moreover, it adopts a hyper-tree structure and an H-cubing

DeEPs A New Instance%2DBased Lazy Discovery and Classification System.

Pushing Aggregate Constraints by Divide%2Dand%2DApproximate.
Iceberg-cube mining is to compute the GROUP BY partitions, for all GROUP BY dimension lists, that satisfy a given aggregate constraint. Previous works have pushed anti-monotone constraints into iceberg-cube mining. However, many useful constraints are not anti-monotone. In this paper, we propose a novel strategy for pushing general aggregate constraints, called Divide-and-Approximate. This strategy divides the search space and approximates the constraint in subspaces by a pushable constraint. As the strategy is recursively applied, the approximation approaches the given constraint and the pruning tights up. We show that all constraints defined by SQL aggregates, arithmetic operators and comparison operators can be pushed by Divideand -Approximate. We present an efficient implementation for an important subclass and evaluate it on both synthetic and real life databases.
On the decidability of the termination problem of active database systems.

Advances in Web%2DAge Information Management

Pushing Aggregate Constraints by Divide%2Dand%2DApproximate.
Iceberg-cube mining is to compute the GROUP BY partitions, for all GROUP BY dimension lists, that satisfy a given aggregate constraint. Previous works have pushed anti-monotone constraints into iceberg-cube mining. However, many useful constraints are not anti-monotone. In this paper, we propose a novel strategy for pushing general aggregate constraints, called Divide-and-Approximate. This strategy divides the search space and approximates the constraint in subspaces by a pushable constraint. As the strategy is recursively applied, the approximation approaches the given constraint and the pruning tights up. We show that all constraints defined by SQL aggregates, arithmetic operators and comparison operators can be pushed by Divideand -Approximate. We present an efficient implementation for an important subclass and evaluate it on both synthetic and real life databases.
Incremental recomputation in local languages.
We study the problem of maintaining recursively-dened views, such as the transitive closure of  a relation, in traditional relational languages that do not have recursion mechanisms. The main  results of this paper are negative ones: we show that a certain property of query languages implies  impossibility of such incremental maintenance. The property we use is locality of queries, which  is known to hold for relational calculus and various extensions, including those with grouping and  aggregate constructs (essentially, plain SQL).  1 
Online Analytical Processing Stream Data Is It Feasible%3F
Real-time surveillance systems and other dynamic environ- ments often generate tremendous (potentially infinite) vol- ume of stream data: the volume is too huge to be scanned multiple times. However, much of such data resides at rather low level of abstraction, whereas most analysts are interested in dynamic changes (such as trends and outliers) at relatively high levels of abstraction. To discover such high level characteristics, one may need to perform on-line multi-level analysis of stream data, similar to OLAP (on-line analytical processing) of relational or data warehouse data.
On Computing Condensed Frequent Pattern Bases.
Frequent pattern mining has been studied extensively. However, the effectiveness and efficiency of this mining is often limited, since the number of frequent patterns generated is often too large. In many applications it is sufficient to generate and examine only frequent patterns with support frequency in close-enough approximation instead of in full precision. Such a compact but close-enough frequent pattern base is called a condensed frequent patterns-base.
CubeExplorer online exploration of data cubes.

Multi%2DDimensional Regression Analysis of Time%2DSeries Data Streams.
Real-time production systems and other dynamic environments often generate tremendous (potentially infinite) amount of stream data; the volume of data is too huge to be stored on disks or scanned multiple times. Can we perform on-line, multi-dimensional analysis and data mining of such data to alert people about dramatic changes of situations and to initiate timely, high-quality responses? This is a challenging task. In this paper,
Efficient Mining of Niches and Set Routines.
Abstract. It is widely recognized that successful businesses usually fall into set routines and become limited by their past. To remain successful, they need to discover new opportunities and niches. Niches are surprising rules that contradict the set routines; they capture significant, representative client sectors that deserve new, more profitable treatments; they are not merely strong-rule and exception pairs. In this paper we study the efficient mining of set routines and niches. We also introduce a semantic approach to select a set of representative patterns, and present an efficient incremental algorithm to implement the approach.
Combining the Strength of Pattern Frequency and Distance for Classification.
where prediction is performed after training instances are provided, has been intensively studied in the machine learning and pattern recognition communities over a long period of time. Instance-based induction [2], contrast to eager-learning based classification (as exemplified by C4.5 [17]), is an important approach to classification. A typical example of instance-based induction algorithms is the k-nearest neighbour (k-NN) rule [4]. Given a test instance T and a database of training instances, the k-NN rule finds k training instances which are the nearest to T according to some kind of distance, and chooses the class label prevailing among these training instances.
Building Behaviour Knowledge Space to Make Classification Decision.

Making Use of the Most Expressive Jumping Emerging Patterns for Classification.
. Classification aims to discover a model from training data that can  be used to predict the class of test instances. In this paper, we propose the use  of jumping emerging patterns (JEPs) as the basis for a new classifier called the  JEP-Classifier. Each JEP can capture some crucial difference between a pair of  datasets. Then, aggregating all JEPs of large supports can produce more potent  classification power. Procedurally, the JEP-Classifier learns the pair-wise features  (sets of JEPs) contained in the training data, and uses the collective impacts contributed  by the most expressive pair-wise features to determine the class labels of  the test data. Using only the most expressive JEPs in the JEP-Classifier strengthens  its resistance to noise in the training data, and reduces its complexity (as there  are usually a very large number of JEPs). We use two algorithms for constructing  the JEP-Classifier which are both scalable and efficient. These algorithms make  use of the border...
Efficient Computation of Iceberg Cubes with Complex Measures.
 It is often too expensive to compute and materialize a complete high-dimensional data cube. Computing an iceberg cube, which contains only aggregates above certain thresholds, is an effective way to derive nontrivial multidimensional aggregations for OLAP and data mining. In this paper, we study efficient methods for computing iceberg cubes with some popularly used complex measures, such as average, and develop a methodology that adopts a weaker but anti-monotonic condition for testing and pruning search space. In particular, for efficient computation of iceberg cubes with the average measure, we propose a top-k average pruning method and extend two previously studied methods, Apriori and BUC, to Top-k Apriori and Top-k BUC. To further improve the performance, an interesting hypertree structure, called H-tree, is designed and a new iceberg cubing method, called Top-k H-Cubing, is developed. Our performance study shows that Top-k BUC and Top-k H-Cubing are promising candidates for scalable computation, and Top-k H-Cubing has the best performance in many cases. 
Mining Multi%2DDimensional Constrained Gradients in Data Cubes.
1 Introduction In recent years, there have been growing interests in multi-dimensional analysis of relational databases, transactional
Making Use of the Most Expressive Jumping Emerging Patterns for Classification.
. Classification aims to discover a model from training data that can  be used to predict the class of test instances. In this paper, we propose the use  of jumping emerging patterns (JEPs) as the basis for a new classifier called the  JEP-Classifier. Each JEP can capture some crucial difference between a pair of  datasets. Then, aggregating all JEPs of large supports can produce more potent  classification power. Procedurally, the JEP-Classifier learns the pair-wise features  (sets of JEPs) contained in the training data, and uses the collective impacts contributed  by the most expressive pair-wise features to determine the class labels of  the test data. Using only the most expressive JEPs in the JEP-Classifier strengthens  its resistance to noise in the training data, and reduces its complexity (as there  are usually a very large number of JEPs). We use two algorithms for constructing  the JEP-Classifier which are both scalable and efficient. These algorithms make  use of the border...
Emerging Patterns and Classification.

Optimization Techniques for Data%2DIntensive Decision Flows.

The Space of Jumping Emerging Patterns and Its Incremental Maintenance Algorithms.
The concept of jumping emerging patterns  (JEPs) has been proposed to describe those discriminating  features which only occur in the positive  training instances but do not occur in the  negative class at all; JEPs have been used to  construct classifiers which generally provide better  accuracy than the state-of-the-art classifiers  such as C4.5. The algorithms for maintaining the  space of jumping emerging patterns (JEP space)  are presented in this paper. We prove that JEP  spaces satisfy the property of convexity. Therefore  JEP spaces can be concisely represented  by two bounds: consisting respectively of the  most general elements and the most specific elements.  In response to insertion of new training  instances, a JEP space is modified by operating  on its boundary elements and the boundary elements  of the JEP spaces associated with the new  instances. This strategy completely avoids the  need to go back to the most initial step to build  the new JEP space. In addition, our ...
Information%2DBased Classification by Aggregating Emerging Patterns.
Abstract. Emerging patterns (EPs) are knowledge patterns capturing contrasts between data classes. In this paper, we propose an informationbased approach for classification by aggregating emerging patterns. The constraint-based EP mining algorithm enables the system to learn from large-volume and high-dimensional data; the new approach for selecting representative EPs and efficient algorithm for finding the EPs renders the system high predictive accuracy and short classification time. Experiments on many benchmark datasets show that the resulting classifiers have good overall predictive accuracy, and are often also superior to other state-of-the-art classification systems such as C4.5, CBA and LB.
Exploring constraints to efficiently mine emerging patterns from large high%2Ddimensional datasets.
Emerging patterns (EPs) were proposed recently to capture changes or differences between datasets: an EP is a multivariate feature whose support increases sharply from a background dataset to a target dataset, and the support ratio is called its growth rate. Interesting long EPs often have low support; mining such EPs from high-dimensional datasets is a great challenge due to the combinatorial explosion of the number of candidates. We propose a Constraint-based EP Miner, ConsEPMiner, that utilizes two types of constraints for effectively pruning the search space: External constraints are user-given minimums on support, growth rate, and growth-rate improvement to con ne the resulting EP set. Inherent constraints -- same subset support, top growth rate, and same origin -- are derived from the properties of EPs and datasets, and are solely for pruning the search space and saving computation. ConsEPMiner can efficiently mine all EPs at low support on large high-dimensional datasets, with low minim...
Making Use of the Most Expressive Jumping Emerging Patterns for Classification.
. Classification aims to discover a model from training data that can  be used to predict the class of test instances. In this paper, we propose the use  of jumping emerging patterns (JEPs) as the basis for a new classifier called the  JEP-Classifier. Each JEP can capture some crucial difference between a pair of  datasets. Then, aggregating all JEPs of large supports can produce more potent  classification power. Procedurally, the JEP-Classifier learns the pair-wise features  (sets of JEPs) contained in the training data, and uses the collective impacts contributed  by the most expressive pair-wise features to determine the class labels of  the test data. Using only the most expressive JEPs in the JEP-Classifier strengthens  its resistance to noise in the training data, and reduces its complexity (as there  are usually a very large number of JEPs). We use two algorithms for constructing  the JEP-Classifier which are both scalable and efficient. These algorithms make  use of the border...
Instance%2DBased Classification by Emerging Patterns.
. Emerging patterns (EPs), namely itemsets whose supports change significantly  from one class to another, capture discriminating features that sharply  contrast instances between the classes. Recently, EP-based classifiers have been  proposed, which first mine as many EPs as possible (called eager-learning) from  the training data and then aggregate the discriminating power of the mined EPs  for classifying new instances. We propose here a new, instance-based classifier  using EPs, called DeEPs, to achieve much better accuracy and efficiency than  the previously proposed EP-based classifiers. High accuracy is achieved because  the instance-based approach enables DeEPs to pinpoint all EPs relevant to a test  instance, some of which are missed by the eager-learning approaches. High efficiency  is obtained using a series of data reduction and concise data-representation  techniques. Experiments show that DeEPs&#039; decision time is linearly scalable over  the number of training instances and...
Separating Auxiliary Arity Hierarchy of First%2DOrder Incremental Evaluation Systems Using %283k 1%29%2Dary Input Relations.

Incremental Maintenance of Recursive Views Using Relational Calculus%2FSQL.
Views are a central component of both traditional database systems and new applications such as data warehouses. Very often the desired views (e.g. the transitive closure) cannot be defined in the standard language of the underlying database system. Fortu-nately, it is often possible to incrementally maintain these views using the standard language. For exam-ple, transitive closure of acyclic graphs, and of undi-rected graphs, can be maintained in relational cal-culus after both single edge insertions and deletions. Many such results have been published in the theoret-ical database community. The purpose of this survey is to make these useful results known to the wider database research and development community. There are many interesting issues involved in the maintenance of recursive views. A maintenance al-gorithm may be applicable to just one view, or to a class of views specified by a view definition language such as Datalog. The maintenance algorithm can be specified in a maintenance language of different ex-pressiveness, such as the conjunctive queries, the re-lational calculus or SQL. Ideally, this maintenance language should be less expensive than the view def-inition language. The maintenance algorithm may allow updates of different kinds, such as just single tu-ple insertions, just single tuple deletions, special set-based insertions and/or deletions, or combinations thereof. The view maintenance algorithms may also need to maintain auxiliary relations to help maintain the views of interest. It is of interest to know the minimal arity necessary for these auxiliary relations
Local properties of query languages.
. Expressiveness of database query languages remains the major  motivation for research in finite model theory. However, most techniques  in finite model theory are based on Ehrenfeucht-Fraisse games,  whose application often involves a rather intricate argument. Furthermore,  most tools apply to first-order logic and some of its extensions,  but not to languages that resemble real query languages, like SQL.  In this paper we use locality to analyze expressiveness of query languages.  A query is local if, to determine if a tuple belongs to the output,  one only has to look at a certain predetermined portion of the input.  We study local properties of queries in a context that goes beyond  the pure first-order case, and then apply the resulting tools to analyze  expressive power of SQL-like languages. We first prove a general result  describing outputs of local queries, that leads to many easy inexpressibility  proofs. We then consider a closely related bounded degree property,  which d...

A Framework for Optimizing Distributed Workflow Executions.
: A central problem in workflow concerns optimizing the distribution of work in a workflow: how should the execution of tasks and the management of tasks be distributed across multiple processing nodes (i.e., computers). In some cases task management and or execution may be at a processing node with limited functionality. For this reason, it is useful to optimize translations of (sub-)workflow schemas into flowcharts, that can be executed in a restricted environment, e.g., in a scripting language or using a flowchart-based workflow engine.  This paper presents a framework for optimizing the physical distribution of workflow schemas, and the mapping of sub-workflow schemas into flowcharts. We provide a general model for representing essentially any distribution of a workflow schema, and for representing a broad variety of execution strategies. The model is based on families of &#034;communicating flowcharts&#034; (CFs). In the framework, a workflow schema is first rewritten as a family of CFs whi...

Efficient Mining of Partial Periodic Patterns in Time Series Database.
Partial periodicity search, i.e., search for partial periodic patterns in time-series databases, is an interesting data mining problem. Previous studies on periodicity search mainly consider finding full periodic patterns, where every point in time contributes (precisely or approximately) to the periodicity. However, partial periodicity is very common in practice since it is more likely that only some of the time episodes may exhibit periodic patterns. We present several algorithms for efficient mining of partial periodic patterns, by exploring some interesting properties related to partial periodicity, such as the Apriori property and the max-subpattern hit set property, and by shared mining of multiple periods. The max-subpattern hit set property is a vital new property which allows us to derive the counts of all frequent patterns from a relatively small subset of patterns existing in the time series. We show that mining partial periodicity needs only two scans over the time series database, even for mining multiple periods. The performance study shows our proposed methods are very efficient in mining long periodic patterns.
Data Integration by Describing Sources with Constraint Databases.

Incremental FO%28 
 Databases provide one of the main concrete scenarios for finitemodel theory within computer science. This paper presents an informal overview of database theory aimed at finite-model theorists, emphasizing the specificity of the database area. It is argued that the area of databases is a rich source of questions and vitality for finite-model theory.
Decidability of First%2DOrder Logic Queries over Views.
. We study the problem of deciding satisfiability of first order logic queries over views, our aim being to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research, due to their role in applications such as information integration and data warehousing. Our principal result is the identification of an important decidable class of queries over unary conjunctive views. This extends the decidability of the classical class of first order sentences over unary relations (the Lowenheim class). We then demonstrate how extending this class leads to undecidability. In addition to new areas, our work also has relevance to extensions of results for related problems such as query containment, trigger termination, implication of dependencies and reasoning in description logics. Key words: satisfiability, decidability, first order logic, database queries, database views, conjunctive queries, unary views, ine...
Efficient Mining of Emerging Patterns Discovering Trends and Differences.
We introduce a new kind of patterns, called emerging patterns (EPs), for knowledge discovery from databases. EPs are defined as itemsets whose supports increase significantly  from one dataset to another. EPs can capture emerging trends in timestamped databases, or useful contrasts between data classes. EPs have been proven useful: we have used them to build very powerful classifiers, which are more accurate than C4.5 and CBA, for many datasets. We believe that EPs with low to medium support, such as 1%-- 20%, can give useful new insights and guidance to experts, in even &#034;well understood&#034; applications.  The efficient mining of EPs is a challenging problem, since (i) the Apriori property no longer holds for EPs, and (ii) there are usually too many candidates for high dimensional databases or for small support thresholds such as 0.5%. Naive algorithms are too costly. To solve this problem, (a) we promote the description of large collections of itemsets using their concise borders (the pa...
Efficient Mining of High Confidience Association Rules without Support Thresholds.

Declarative workflows that support easy modification and dynamic browsing.

Interestingness of Discovered Association Rules in Terms of Neighborhood%2DBased Unexpectedness.
One of the central problems in knowledge discovery is the development of good measures of interestingness of discovered patterns. With such measures, a user needs to manually examine only the more interesting rules, instead of each of a large number of mined rules. Previous proposals of such measures include rule templates, minimal rule cover, actionability, and unexpectedness in the statistical sense or against user beliefs. In this paper we will introduce neighborhood-based interestingness by considering unexpectedness in terms of neighborhood-based parameters. We first present some novel notions of distance between rules and of neighborhoods of rules. The neighborhood-based interestingness of a rule is then defined in terms of the pattern of the fluctuation of confidences or the density of mined rules in some of its neighborhoods. Such interestingness can also be defined for sets of rules (e.g. plateaus and ridges) when their neighborhoods have certain properties. We c...
Decidability and Undecidability Results for the Termination Problem of Active Database Rules.
Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers&#039;. One of the principal questions for such systems is that of termination - is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present two families of rule languages, the one literal languages where each update is permitted to have just one atom in its body, and the unary languages where only unary relations may be updated, but higher arity relations may be accessed through views. Within each of these, we identify members close to the boundary of (un)decidability. Our context is similar to the while query language and the dynamics gives an interesting contrast to Datalog with negation; our results shed insights on the power of triggers as well as comparison of the termination problem to boundedness and query containment.
Incremental View Maintenance By Base Relation Tagging in Distributed Databases.
. The incremental view maintenance problem deals with the efficient updating of materialized views in response to updates to base relations. This paper considers the problem in a distributed database environment, with communication cost minimization as the primary objective. The views considered are defined based on the relational join operation. The approach is to use &#034;yes&#034;/&#034;no&#034; tags as auxiliary data on tuples in the base relations to indicate whether the tuples participate in joins. These tags will help avoid sending irrelevant data over the network and thus reduce the communication cost. Two basic view maintenance algorithms are proposed using the tags. In addition to reducing communication costs, an important feature of these two basic algorithms is that they derive the &#034;exact change&#034; to views without looking at the old views. This feature allows us to maintain certain aggregates on views without actually materializing the views themselves; this feature is useful in applications s...
Relational Expressive Power of Constraint Query Languages.
The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic boolean queries under both the natural and active-domain semantics. In the course of proving...
Arity Bounds in First%2DOrder Incremental Evaluation and Definition of Polynomial Time Database Queries.

Maintaining Constrained Transitive Closure by Conjunctive Queries.

Local Properties of Query Languages.
. Expressiveness of database query languages remains the major  motivation for research in finite model theory. However, most techniques  in finite model theory are based on Ehrenfeucht-Fraisse games,  whose application often involves a rather intricate argument. Furthermore,  most tools apply to first-order logic and some of its extensions,  but not to languages that resemble real query languages, like SQL.  In this paper we use locality to analyze expressiveness of query languages.  A query is local if, to determine if a tuple belongs to the output,  one only has to look at a certain predetermined portion of the input.  We study local properties of queries in a context that goes beyond  the pure first-order case, and then apply the resulting tools to analyze  expressive power of SQL-like languages. We first prove a general result  describing outputs of local queries, that leads to many easy inexpressibility  proofs. We then consider a closely related bounded degree property,  which d...
Structural Issues in Active Rule Systems.
Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers&#039;. There is little consensus, though, on what components should be included in a rule system. In this paper, the expressive power of some simple active database rule systems is examined and the effect of choosing different features studied. Four important parameters of variation are presented, namely the rule language, the external query language, the meta rule language and the pending rule structure. We show that each of these is highly influential in determining the expressiveness of the rule system as a whole, and that an appreciation of them can serve as a basis for understanding the broader picture of system behaviour.
Deterministic FOIES are Strictly Weaker.

Some Relationships between the FOIES and S1 Arity Hierarchies.

Maintaining Transitive Closure in First Order After Node%2DSet and Edge%2DSet Deletions.

Algorithms for Adapting Materialised Views in Data Warehouses.
In this paper we consider the problem of materialised view adaptation in data warehouses. Materialised views are important in data warehousing where they are used to speed up query processing on large amounts of data. User requirements change over time, which may change the definitions of views dynamically. For such situations, the question arises whether the materialised views should be recomputed from scratch for every change in the definition or they should be obtained by adapting old materialised views. Changes to a view definition may be expensive, if the view is recomputed from scratch. Therefore, it is worthwhile to examine ways of performing changes to the materialised view without recomputing the entire view which has undergone a change in definition. We present adaptation algorithms for adapting views when the changes are made in each SELECT, FROM, and WHERE clause. The main idea of our algorithms is to augment the schemas of base relations by adding `joincount &#039; attributes t...
Relational Expressive Power of Constraint Query Languages.
The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic boolean queries under both the natural and active-domain semantics. In the course of proving...
Conjunctive Query Containment with Respect to Views and Constraints.

On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL.
We study the problem of maintaining recursively-defined views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. In particular, we show that the transitive closure cannot be maintained in relational calculus under deletion of edges. We use new proof techniques to show this result. These proof techniques generalize to other languages, for example, to the language for nested relations that also contains a number of aggregate functions. Such a language is considered in this paper as a theoretical reconstruction of SQL. Our proof techniques also generalize to other recursive queries. Consequently, we show that a number of recursive queries cannot be maintained in an SQL-like language. We show that this continues to be true in the presence of certain auxiliary relations. We also relate the complexity of updating transitive closure to that of updating the same-generation query and show that the latter is strictly harder t...
Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries.
Abstract. Given a recursive (datalog) query, the nonrecursive incremental evaluation approach uses nonrecursive (datalog) programs to compute the difference of the answers to the query against successive databases between updates. The mechanism used in this approach is called a “First-Order Incremental Evaluation System ” (FOIES). We show that for two large classes of datalog queries, called “generalized (weakly) regular queries”, FOIES always exist. We also define “increment boundedness ” and its variations, which generalize boundedness. Increment bounded queries are shown to have FOIES of certain forms. We also relate increment boundedness to structural recursion, which was proposed for bulk data types. We characterize increment boundednessusing the “insertion idempotency”, “insertion commutativity”, and “determinism ” properties of structural recursion. Finally, we show that the increment boundedness notions are undecidable and a decidable sufficient condition is given. 1
Space%2DBounded FOIES.

Nonrecursive Incremental Evaluation of Datalog Queries.
We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process &#034;incremental query evaluation using conjunctive queries.&#034; After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries havin...
Incremental and Decremental Evaluation of Transitive Closure by First%2DOrder Queries

On the Index of Positive Programmed Formal Languages.

On Decompositions of Chain Datalog Programs into P %28left%2D%29linear 1%2Drule Components.

A Framework for Object Migration in Object%2DOriented Databases.

First%2DOrder Incremental Evaluation of Datalog Queries.
We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use first-order queries to compute the differences, and call this process &#034;first-order incremental query evaluation.&#034; After formalizing the notion of first-order incremental query evaluation, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries having the so-called cartesian-closed increment property, and to the case of unbound...
On the Monotonicity of %28LDL%29 Logic Programs with Set.

Representation and Translation of Queries in Heterogeneous Databases with Schematic Discrepancies.

Discussion Report Object Migration and Classification.

Incremental Evaluation of Datalog Queries.
We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process &#034;incremental query evaluation using conjunctive queries.&#034; After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries havin...
Datalog Expressiveness of Chain Queries Grammar Tools and Characterizations.

On Datalog Linearization of Chain Queries.

Object Behaviors and Scripts.
. We speculate on the possibilities for a realization of the idea of a threedimensional Cyberspace, as sketched in the novels of William Gibson using today&#039;s technology. Virtual reality and global networks such as the Internet together can provide the fundamentals for such an effort. From an examination of the technological principles of a Gibsonian virtual environment, we conclude what properties such an implementation must have. An implementation of a system with these properties faces a number of problems in the large and in the small; especially, the semantics of the virtual environment and its inhabitants must be defined. We also report on our ongoing implementation of a prototype software system which was designed to evaluate the feasibility of these ideas.  1. Introduction  In his famous novel &#034;Neuromancer&#034; [Gibs84], William Gibson presents the idea of the Cyberspace, a sensual representation of a global, networked database that is presented to the user directly by brain stimula...
On the Monotonicity of %28LDL%29 Logic Programs with Sets.

Localizable Constraints for Object Histories.

On the Decomposition of Datalog Program Mappings.

On Distributed Processibility of Datalog Queries by Decomposing Databases.

On the Composition and Decomposition of Datalog Program Mappings.

Localizable Constraints for Object Histories.

